// BinaryTree.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include"BinaryTreeBase.h"
#include"BinaryTreeLevel.h"
#include"BianryTreeTravelLoop.h"
#include"BinarySearchTree.h"

int main()
{
    BinaryTreeNode* binaryTree = nullptr;
    //CreateBinaryTree(&binaryTree);

    //              a
    //          b           c
    //      d     #      f      g
    //    #  h         i  #   #   #
    //      # #       # #
    const char* data = "abd#h###cfi###g##";
    int index = 0;
    CreateBinaryTree(&binaryTree, data, &index);

    cout << "前序遍历" << endl;
    PreTravelBinaryTree(binaryTree);

    cout << endl << "中序遍历" << endl;
    InTravelBinaryTree(binaryTree);

    cout << endl << "后序遍历" << endl;
    BackTravelBinaryTree(binaryTree);

    cout << endl << "层序遍历" << endl;
    LevelTravelBinaryTree(binaryTree);

    cout << endl << endl;
    cout << "迭代的方式前序遍历" << endl;
    PreTravelBinaryTreeLoop(binaryTree);

    cout << endl;
    cout << "迭代的方式中序遍历" << endl;
    InTravelBinaryTreeLoop(binaryTree);

    cout << endl;
    cout << "迭代的方式后序遍历" << endl;
    BackTravelBinaryTreeLoop(binaryTree);

    cout << endl << endl;
    //          6
    //      5       7
    //   3            19
    //      4       10  20
    //            9
    BSTNodeTree tree;
    int arrayBST[9] = {6, 7, 5, 19, 3, 10, 4, 20, 9};
    BinarySearchTreeNode* T = new BinarySearchTreeNode();
    T->data = arrayBST[0];
    T->Parent = nullptr;
    T->LChild = nullptr;
    T->RChild = nullptr;
    for (int i = 1; i < 9; i++) {
        BSTInsert(T, arrayBST[i]);
        tree.InsertNode(arrayBST[i]);   //cpp 迭代方式插入节点
    }
    cout << "BST 前序遍历" << endl;
    PreTravelBinarySearchTree(T);
    cout << endl << "BST 中序遍历" << endl;
    InTravelBinarySearchTree(T);    //中序遍历即排序结果
    cout << endl << "BST 后序遍历" << endl;
    BackTravelBinarySearchTree(T);

    cout << endl;
    cout << "cpp BST 前序遍历" << endl;
    PreTravelBinarySearchTree(tree.Head);

    cout << endl;
    BSTNode* precursor = FindPrecursor(T);
    cout << "T 的前驱节点: " << precursor->data << endl;

    BSTNode* posterior = FindPosterior(T);
    cout << "T 的后继节点: " << posterior->data << endl;

    BSTDelete(T, 10);
    cout << endl << "删除节点 10 前序遍历" << endl;
    PreTravelBinarySearchTree(T);

    BSTDelete(T, 19);
    cout << endl << "删除节点 19 前序遍历" << endl;
    PreTravelBinarySearchTree(T);

    BSTDelete(T, 6);
    cout << endl << "删除节点 6 前序遍历" << endl;
    PreTravelBinarySearchTree(T);
}